#include "grate_test_utils.h"
#include "grate/eigenvalue.h"
#include "grate/dfa.h"

using growth_rate::DFAInterface;
using growth_rate::LexminTrie;
using growth_rate::LexminDFA;
using growth_rate::testing::TableDFA;
using growth_rate::EigenvalueOptions;
using growth_rate::EigenvalueCalculator;

namespace {

static const size_t kMaxTestIterations = 5000;

class EigenvalueTest : public ::testing::Test {
 protected:
  void test_with_options(const EigenvalueOptions &options) {
    sample_dfa_.clear();
    build_sample_dfa();
    for (size_t i = 0; i < sample_dfa_.size(); i++) {
      DFAInterface *dfa = sample_dfa_[i].first;
      double exp_result = sample_dfa_[i].second;
      if (exp_result == 0.0 && options.add_loops_to_nodes &&
          options.use_oracle) {
        // Oracle-based algorithm converges to zero answer too slowly
        // if we add loops to nodes.
        continue;
      }
      size_t iterations;
      double result = EigenvalueCalculator::get_max_eigenvalue(
          dfa, options, &iterations);
      EXPECT_FALSE(-1.0 == result);
      EXPECT_NEAR(exp_result, result, options.precision);
      EXPECT_LT(iterations, kMaxTestIterations);
    }
  }

 private:
  void build_sample_dfa() {
    ASSERT_EQ(0U, sample_dfa_.size());

    // Create sample DFAs.
    {
      // Chain DFA.
      int exp_table[] = {1, 1,
                         2, 1,
                         3, 1,
                         -1, 1};
      TableDFA *chain_dfa = new TableDFA(4, 2, exp_table);
      // TODO(samsonov): Actually check the answers for sample DFAs.
      sample_dfa_.push_back(std::make_pair(chain_dfa, 1.8392867554360488));
    }

    {
      // Small DFA.
      int exp_table[] = {1, 1, 1,
                         5, 2, 2,
                         3, 7, 2,
                         4, 3, 2,
                         5, -1, -1,
                         5, 6, 6,
                         3, 7, -1,
                         6, 5, -1};
      TableDFA *small_dfa = new TableDFA(8, 3, exp_table);
      sample_dfa_.push_back(std::make_pair(small_dfa, 2.4709793798332216));
    }

    {
      // Big alphabet DFA.
      int exp_table[] = {1, 1, 1, 1, 1, 1, 1,
                         1, -1, -1, -1, -1, -1, -1};
      TableDFA *big_alph_dfa = new TableDFA(2, 7, exp_table);
      sample_dfa_.push_back(std::make_pair(big_alph_dfa, 1.0));
    }

    {
      LexminTrie zero_grate_trie(10, 3);
      EXPECT_TRUE(zero_grate_trie.add_lexmin_word("aa"));
      EXPECT_TRUE(zero_grate_trie.add_lexmin_word("ab"));
      LexminDFA *zero_grate_dfa = new LexminDFA(&zero_grate_trie);
      sample_dfa_.push_back(std::make_pair(zero_grate_dfa, 0.0));
    }
    // TODO(samsonov): Add more tests here.
  }

  // Sample DFAs and their max eigenvalues.
  std::vector<std::pair<DFAInterface*, double> > sample_dfa_;
};

TEST_F(EigenvalueTest, DefaultOptionsTest) {
  test_with_options(EigenvalueOptions());
}

TEST_F(EigenvalueTest, AllPossibleOptionsTest) {
  const double precisions[] = {1e-5, 1e-6, 1e-7, 1e-8};
  for (size_t prec = 0; prec < ARRAYSIZE(precisions); ++prec) {
    for (size_t loops = 0; loops < 2; loops++) {
      for (size_t oracle = 0; oracle < 2; oracle++) {
        for (size_t edge_list = 0;
             edge_list < EigenvalueOptions::EdgeListModeCnt; edge_list++) {
          EigenvalueOptions options;
          options.precision = precisions[prec];
          // Use default value for max_iterations.
          options.add_loops_to_nodes = (loops > 0);
          options.use_oracle = (oracle > 0);
          options.generate_edge_list_mode =
            static_cast<EigenvalueOptions::GenerateEdgeListMode>(edge_list);
          // Test w/o finding SCC.
          if (options.use_oracle) {
            options.scc_strategy = EigenvalueOptions::FindSccNever;
            test_with_options(options);
          }
          // Test default algorithm for SCC.
          options.scc_strategy = EigenvalueOptions::FindSccDefault;
          test_with_options(options);
          // TODO(samsonov): Add test for FindSccAssumeSingle when it's ready.
        }
      }
    }
  }
}

}  // namespace
